package org.example.myleet.p638;

import java.util.List;

public class Solution {

    /**
     * 共需要采购n种商品
     */
    private int n;

    /**
     * 最小花费
     */
    private int minCost;

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        n = price.size();
        for (int i = 0; i < n; ++i) {
            //啥礼包都不选，直接原价购买，应该是最大消费了
            minCost += price.get(i) * needs.get(i);
        }
        dfsDynamic(price, special, needs, new int[n], 0);
        return minCost;
    }

    /**
     * 在当前状态下对每一种礼包都尝试一下，尝试完一种礼包要进行一次回溯，得到下一种状态，并递归
     * @param price 原价
     * @param special 大礼包
     * @param needs 购物清单
     * @param cart 当前购物车包含的商品
     * @param cost 当前购物车包含商品时需要的支出
     */
    private void dfsDynamic(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int[] cart, int cost) {
        for (List<Integer> specialBag : special) {
            if (canAddCart(needs, specialBag, cart)) {
                //如果这个大礼包可以加入购物车，就先加入购物车，并加上这个支出
                addCart(specialBag, cart);
                cost += specialBag.get(n);
                if (completeCart(needs, cart)) {
                    //购物车已经满足购物清单，取最低支出
                    minCost = Math.min(minCost, cost);
                } else {
                    //购物车未满足购物清单，尝试剩余的商品按原价直接购买的支出是否更低
                    int directCost = calculateDirectCost(price, needs, cart, cost);
                    minCost = Math.min(minCost, directCost);
                    //购物车未满足购物清单，尝试下一个大礼包
                    dfsDynamic(price, special, needs, cart, cost);
                }
                //回溯
                recoverCart(specialBag, cart);
                cost -= specialBag.get(n);
            }
        }
    }

    /**
     * 判断大礼包能不能加入购物车
     */
    private boolean canAddCart(List<Integer> needs, List<Integer> specialBag, int[] cart) {
        for (int i = 0; i < n; ++i) {
            if (cart[i] + specialBag.get(i) > needs.get(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 大礼包加入购物车
     */
    private void addCart(List<Integer> specialBag, int[] cart) {
        for (int i = 0; i < n; ++i) {
            cart[i] += specialBag.get(i);
        }
    }

    /**
     * 将大礼包移除出购物车
     */
    private void recoverCart(List<Integer> specialBag, int[] cart) {
        for (int i = 0; i < n; ++i) {
            cart[i] -= specialBag.get(i);
        }
    }

    /**
     * 购物车未满足清单的商品直接按原价直接购买的支出
     */
    private int calculateDirectCost(List<Integer> price, List<Integer> needs, int[] cart, int cost) {
        int directCost = cost;
        for (int i = 0; i < n; ++i) {
            directCost += (needs.get(i) - cart[i]) * price.get(i);
        }
        return directCost;
    }

    /**
     * 判断购物车是不是满足购物清单
     */
    private boolean completeCart(List<Integer> needs, int[] cart) {
        for (int i = 0; i < n; ++i) {
            if (cart[i] != needs.get(i)) {
                return false;
            }
        }
        return true;
    }
}
